package br.ufmg.vod.wbr.algorithims.components;

import javolution.util.FastList;
import br.ufmg.vod.collections.IntStack;
import br.ufmg.vod.wbr.algorithims.SimulateAtack;
import br.ufmg.vod.wbr.algorithims.dfs.DFS;
import br.ufmg.vod.wbr.algorithims.dfs.DFSData;
import br.ufmg.vod.wbr.algorithims.dfs.RecursiveDFS;
import br.ufmg.vod.wbr.api.DirectedGraph;

public class StronglyConnectedComponentsDFS implements Runnable{
	
	private final DirectedGraph graph;
	FastList<int[]> components;
	int[] giantComponent;
	private SimulateAtack attackSimulator;
	private int numNodesUnderAttack;
	
	public StronglyConnectedComponentsDFS(DirectedGraph graph){
		this.graph = graph;
		components = new FastList<int[]>();
	}
	
	public void setAttackSimulator(SimulateAtack attackSimulator, int numNodesUnderAttack){
		this.attackSimulator = attackSimulator;
		this.numNodesUnderAttack = numNodesUnderAttack;
	}
	
	private void simulateAtack(DFSData data) {
		if( this.attackSimulator != null && this.numNodesUnderAttack > 0 )
			this.attackSimulator.newAtack(this.numNodesUnderAttack, data);
	}

	@Override
	public void run() {
		
		//RUN 1st DFS
		DFS firstDFS = new RecursiveDFS(graph);
		this.simulateAtack(firstDFS.getData()); //paint black nodes under attack
		firstDFS.dfsAllVertex();
		IntStack firstDFSStack = firstDFS.getData().visitedStack;
		System.out.println("FINISHED 1st DFS!!");
		
		//transpose to run second
		graph.transpose();
		
		
		int giantComponentSize = 0;
		//2nd DFS
		DFS secondDFS = new RecursiveDFS(graph);
		DFSData secondDFSData = secondDFS.getData();
		
		
		while(!firstDFSStack.isEmpty()){
			
			//stack remove
			int vertex = firstDFSStack.pop();
			
			//skip already visited
			if(secondDFSData.colors[vertex]!= DFSData.WHITE) continue;
				
			this.simulateAtack(secondDFS.getData()); //paint black nodes under attack
			//runDFS
			secondDFS.dfsSingleVertex(vertex);
			
			//arrayCopy!
			int[] scComponent = new int[secondDFSData.visitedStack.size()];
//			components.add(secondDFSData.stack.toArray(scComponent));
			components.add( secondDFSData.visitedStack.toArray(scComponent) );
			giantComponent = giantComponent == null || giantComponent.length < scComponent.length ? scComponent : giantComponent;
			
			
			//clear visited stack only!!
			secondDFSData.visitedStack.clear();
			
			
			giantComponentSize = Math.max(giantComponentSize, scComponent.length);
		}
		System.out.println(giantComponentSize+" giant component!");
	}



	public FastList<int[]> getComponents() {
		return components;
	}

	public int[] getGiantComponent() {
		return giantComponent;
	}


}
